package com.lw.leetcode.sort.c;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 2532. 过桥的时间
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/12 9:52
 */
public class FindCrossingTime {


    public static void main(String[] args) {
        FindCrossingTime test = new FindCrossingTime();

        // 6
//        int n = 1;
//        int k = 3;
//        int[][] time = {{1,1,2,1},{1,1,3,1},{1,1,4,1}};

        // 34
//        int n = 2;
//        int k = 2;
//        int[][] time = {{9, 8, 9, 5},{6, 9, 8, 6}};


        // 34
        int n = 9;
        int k = 6;
        int[][] time = {{2,6,9,4},{4,8,7,5},{4,6,7,6},{2,3,3,7},{9,3,6,8},{2,8,8,4}};

        // 6
//        int n = 2;
//        int k = 10;
//        System.out.println(n);
//        System.out.println(k);
//        int[][] time = Utils.getArr(k, 4, 1, 10);
//        System.out.println();

        // 50
//        int n = 3;
//        int k = 2;
//        int[][] time = {{1, 9, 1, 8}, {10, 10, 10, 10}};

        int crossingTime = test.findCrossingTime(n, k, time);
        System.out.println(crossingTime);

    }


    public int findCrossingTime(int n, int k, int[][] time) {
        int[][] arr = new int[k][5];
        for (int i = 0; i < k; i++) {
            int[] as = arr[i];
            int[] bs = time[i];
            as[0] = bs[0];
            as[1] = bs[1];
            as[2] = bs[2];
            as[3] = bs[3];
            as[4] = i;
        }
        Arrays.sort(arr, (a, b) -> a[0] + a[2] == b[0] + b[2] ? Integer.compare(b[4], a[4]) :
                Integer.compare(b[0] + b[2], a[0] + a[2]));
        PriorityQueue<Integer> ls = new PriorityQueue<>();
        PriorityQueue<Long> lp = new PriorityQueue<>();
        PriorityQueue<Integer> rs = new PriorityQueue<>();
        PriorityQueue<Long> rp = new PriorityQueue<>();
        PriorityQueue<Integer> tt = new PriorityQueue<>();
        for (int i = 1; i < k; i++) {
            ls.add(i);
        }
        tt.add(arr[0][0]);
        int run =  arr[0][0];
        int no = 0;
        boolean f = true;
        int t = 0;
        n--;
        while (ls.size() + lp.size() != k  || n > 0) {
            t = tt.poll();
            if (run != -1 && run <= t) {
                int[] ints = arr[no];
                if (f) {
                    rp.add(((t + (long) ints[1]) << 32) + no);
                    tt.add(t + ints[1]);
                } else {
                    lp.add(((t + (long) ints[3]) << 32) + no);
                    tt.add(t + ints[3]);
                }
                run = -1;
            }
            while (!lp.isEmpty()) {
                long p = lp.peek();
                if ((p >> 32) > t) {
                    break;
                }
                lp.poll();
                ls.add((int) p);
            }
            while (!rp.isEmpty()) {
                long p = rp.peek();
                if ((p >> 32) > t) {
                    break;
                }
                rp.poll();
                rs.add((int) p);
            }

            if (run == -1) {
                if (!rs.isEmpty()) {
                    int p = rs.poll();
                    run = t + arr[p][2];
                    f = false;
                    no = p;
                    tt.add(run);
                } else if (!ls.isEmpty() && n > 0) {
                    n--;
                    int p = ls.poll();
                    run = t + arr[p][0];
                    f = true;
                    no = p;
                    tt.add(run);
                }
            }
        }
        return t;
    }

}
